package 二叉树;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    Node left;
    Node right;
    Integer value;

    public Node(Node left, Node right, Integer value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }
}

public class Traverse {


    public static void main(String[] args) {
        Node left = new Node(null, null, 2);
        Node right = new Node(null, null, 3);
        Node node = new Node(left, right, 1);


//        recursion(node);
//        notRecursionBegin(node);
//        notRecursionBack(node);
        sequence(node);
    }

    //递归方式
    public static void recursion(Node node) {
        if (node == null) {
            return;
        }
        //先序 头左右
        recursion(node.left);
        //中序 左头右
        recursion(node.right);
        //后序 左右头
    }

    //非递归方式 用栈的方式 先序遍历
    public static void notRecursionBegin(Node node) {
        if (node != null) {
            Stack<Node> stack = new Stack<>();
            stack.add(node);
            while (!stack.isEmpty()) {
                Node pop = stack.pop();
                System.out.println(pop.value);
                if (pop.right != null) {
                    stack.push(node.right);
                }
                if (pop.left != null) {
                    stack.push(node.left);
                }
            }
        }
    }

    //非递归方式 用栈的方式 后序遍历
    public static void notRecursionBack(Node node) {
        if (node != null) {
            Stack<Node> stack = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack.add(node);
            while (!stack.isEmpty()) {
                Node pop = stack.pop();
                stack2.push(pop);
                if (pop.left != null) {
                    stack.push(node.left);
                }
                if (pop.right != null) {
                    stack.push(node.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.println(stack2.pop().value);
            }
        }
    }

    //层序遍历 有cur出队列，有左入左，有右入右
    public static void sequence(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll == null) {
                return;
            }
            System.out.println(poll.value);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }

        }
    }


}
